1. Field
This disclosure relates generally to data processing systems, and more specifically, to computationally efficient mechanisms for calculating a hash over information that is evaluated, at least partially, in coordination with match rules.
2. Related Art
Modern packet-routed communications involve the use of numerous specialized hardware and software techniques to parse packet headers and to direct flows of related packet information based on the header fields parsed. In some cases, it can be desirable to calculate a hash over at least a portion of the information parsed from individual packet headers so as to deterministically distribute computations or flows in a way that maintains locality with respect to some aspect of the hashed over information. For example, hashes are commonly used in packet routing implementations that seek to achieve load balance by distributing packets over a range of processing queues, targets or other resources.
Typically, packet routing implementations parse field information from headers and evaluate field contents (e.g., source addresses, destination addresses, protocol, etc.) in order to make routing and filtration decisions. In programmable implementations, these evaluations may be coded as match rules. For example, a destination IP address may be masked (to mask away all but a network/sub-network portion of the address) and matched against one or more network/sub-network address codings to determine whether corresponding information should be routed onward and, if so, in what manner.
In some cases, it may be desirable to include in a hash computation certain field contents that are evaluated by match rules. Some implementations of hash techniques and, in particular, some implementations that exhibit good avalanche and diffusion properties, are non-commutative. As a result, different orderings of field values may produce different hash results. In some applications, hash results resulting from different field orderings are all equally valid and useful. However, in some applications or implementations, it may be desirable to ensure that hash results are deterministically computed over some particular ordered set of fields. In general, a set and ordering of fields desirable for purposes of hash computation need not correspond to the set and order of fields evaluated in accord with match rules. Rather, evaluation order will typically correspond to a pertinent decision tree of field match predicates. On the other hand, a desirable ordering for hash computations may trace to factors such as utility the resultant hash at a higher-level protocol, or may trace to design requirements for determinism in the face of rule set revisions and/or varying levels of concurrency across a range of product implementations. In any case, desirable precedence orders for match rule evaluation do not typically (or necessarily) correspond to a desirable ordering of field values over which a hash is computed.
Accordingly, computationally efficient techniques are desired that decouple the ordering of match rule evaluations from that employed in hash computations.
The use of the same reference symbols in different drawings indicates similar or identical items.